\documentclass[a4paper,10pt]{report}
\usepackage[utf8]{inputenc}
\setlength{\parindent}{0mm} 
\usepackage{amsmath}
\usepackage{graphicx}
\title{Assignment 2 Solution}
\author{}

\begin{document}
\maketitle

\begin{tabular}{lll}
Jose Santiago Rodriguez & ptfs162  & santiagoropb@gmail.com\\
Akash Mittal & ptfs161 & akash.mittal@studium.fau.de\\
Bich Ngoc Vu & ptfs184 &  bich.ngoc.vu@studium.fau.de\\
\end{tabular}



\section*{Task 1}
In case a) and b) the compiler can predict the branch in most cases, since it follows the same pattern: either the if-branch is always true or always false. 
In case c) we have random numbers between -1 and 1, here the branch is hard to predict.\\
Now the performance generally depends on the extent of mispredicted branches and the array length $N$(if data has to be fetched from cache or memory).
One can say that the smaller $N$, the bigger the impact of mispredictions on the performance. For large $N$, the performance is indepent on $c[]$ and this problem 
is identical to the vector triad from assignment 1.

\begin{figure}[h]
 \centering
 \includegraphics[width=\textwidth]{./plot_task1.png}
 \caption{Branch prediction}
\end{figure}


\section*{Task 2}
a) $expected~Performance = Throughput * Clockspeed$ \\
$Throughput = N/(L+N)$, where L is the total latency of ne iteration and N the number of operations.\\
The latency consists of 3 cycles for addition, 5 for multiplication and 5 for the two load operations(only one load instruction per cycle possible). 
Because of the dependency on the multiplication, the throughput obtained is $N/(L+3*N)$, where $L = 13$ in this task.\\
Thus the maximum possible performance is $2660 MHz * 1/3 [iterations/s] * 2 =1773 MFlop/s$. \\

b) The performance expected at $N=8$ is $2660 MHz * 8/(13+3*8)*2 = 1150.27 MFlop/s $.\\
To get half the expected value from a), which is $\approx 886 MFlop/s$, we have $1/2 * N(l+3*N) = 1/2 * 1/3 \Rightarrow N=13/3 \approx 3$ \\

c) With AVX loading 4 double values at once is possible. Since adding up the four slots takes 8 more cycles, the latency changes to $L=5+5+11=21$. 
So every 11 cycles we obtain one AVX result. Since we have 4 slots and two operations per cycle, the formula for the maximum possible performance changes to 
$N/(L+11*N) * 8 * Clockspeed  \Rightarrow 8/11 * 2660 MFlop/s = 1934.54 MFlop/s$. For $N=8$: $performance = 8/(21+8*8) * 8 * 2660 MFlop/s = 1561 MFlop/s$. To obtain half of the 
maximum possible performance, $N$  must be $1/2 * N/(L+11*N) = 1/2 * 1/11 \Rightarrow N = 21/11 \approx 2$. But for $N=2$  we don't have enough elements in the array since 
there should at least 4 of them for the vectorization.\\
Using 64 bit registers, the latency remains the same but the maximum performance and also the performance for $N=8$ doubles, since we have 8 slots now. To achieve half of the maximum 
performance, we now need an array of size $N=10$.\\

d)Assuming an add instruction requires three cycles and we now use 2 way modulo unrolling to resolve data dependenciesalong with SIMD vectorization. Now we have two AVX instructions every 3 cycles and
for each AVX instruction $8 Flop$. Then, the maximum performance is $2/3*8*2660 = 14 GFlop/s$. A 4 way unrolling will achieve the maximum performance of $21 GFlop/s$ but since the latency will 
also increase, that won't change anything if $N$ is small.

\end{document}          